//给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
//
//
//
// 示例 1：
//
//
//
//
//输入：head = [1,2,3,4,5], n = 2
//输出：[1,2,3,5]
//
//
// 示例 2：
//
//
//输入：head = [1], n = 1
//输出：[]
//
//
// 示例 3：
//
//
//输入：head = [1,2], n = 1
//输出：[1]
//
//
//
//
// 提示：
//
//
// 链表中结点的数目为 sz
// 1 <= sz <= 30
// 0 <= Node.val <= 100
// 1 <= n <= sz
//
//
//
//
// 进阶：能尝试使用一趟扫描实现吗？
//
//
//
//
// 注意：本题与主站 19 题相同： https://leetcode-cn.com/problems/remove-nth-node-from-end-
//of-list/
//
// Related Topics 链表 双指针 👍 94 👎 0


package LeetCode.editor.cn;


import java.util.Deque;
import java.util.LinkedList;

/**
 * @author ldltd
 * @date 2025-01-20 10:11:25
 * @description LCR 021.删除链表的倒数第 N 个结点

 */

public class SLwz0R {
    public static void main(String[] args) {
    //测试代码
    SLwz0R fun = new SLwz0R();
    Solution solution= fun.new Solution();

    }

//leetcode submit region begin(Prohibit modification and deletion)

  //Definition for singly-linked list.
  public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class Solution {
        //快慢指针或者栈
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode res=new ListNode(0,head);
        ListNode p=res;
        ListNode slow=p;
        ListNode fast=p;
        while (n-->0){
            fast=fast.next;
        }
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        slow.next=slow.next.next;
        return res.next;
    }

    public ListNode removeNthFromEnd1(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        Deque<ListNode> stack = new LinkedList<ListNode>();
        ListNode cur = dummy;
        //先全部入栈
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        //然后依次出栈到删除节点的前一个
        for (int i = 0; i < n; ++i) {
            stack.pop();
        }
        ListNode prev = stack.peek();
        //删除
        prev.next = prev.next.next;
        return dummy.next;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
